1. Field of the Invention
The present invention relates to computer graphics.
2. Related Art
A wide variety of applications rely on computer graphics to generate images. An image is made up of an array of picture elements (pixels) and can be displayed on a display unit, such as, a monitor, screen, or cathode ray tube. Images often include graphical representations of objects. Many different types of computing devices with graphics capabilities are used to generate images. Such computing devices use graphics processing. A combination of software, firmware and/or hardware is used to implement graphics processing. For example, graphics processing including rendering can be carried out in a graphics card, graphics subsystem, graphics processor, graphics or rendering pipeline, and/or a graphics application programming interface (API) and libraries, such as, OPENGL.
In computer graphics, the geometry of an object is represented by primitives. Common primitives are points, lines, and polygons such as triangles or quads. Each primitive is made up of points called vertices. Each vertex includes information relating to the object and its graphical display as an image. For example, vertex information can include, but is not limited to, vertex coordinates, texture coordinates, an alpha value, and a depth value. Vertex coordinates define the location of a respective vertex in a three-dimensional coordinate space (x,y,z), such as, an object coordinate space or a world coordinate space. In this way, vertex coordinates define the geometry of an object surface. Texture coordinates are coordinates that map to an image in a two-dimensional space (s,t) or a three-dimension space (r,s,t). One way this image (also called a texture) is used in graphics processing is to provide additional surface detail to the object. An alpha value is used to represent transparency information. The depth value is used to define depth information.
Increasing demands are being made upon graphics processing. These demands include realism, speed and cost. Realistic images are desired to be rendered at real-time, interactive rates while avoiding burdensome graphics processing or hardware requirements. One way to achieve more realism is to use complex objects. Complex objects, however, can involve a large number of primitives. For example, hundred, thousands, or millions of triangles may be needed to represent complex objects. This increases the number of calculations and other processing work required to render the object.
One approach to accommodating these demands is to approximate geometric information by forming an object proxy. Conventional approaches to forming an object proxy, however, have been limited. For example, Buehler et al. describes use of geometric proxies based on a progressive hull technique described by Sander et al. See, Buehler et al., xe2x80x9cUnstructured Lumigraph Rendering,xe2x80x9d SIGGRAPH 2001, Los Angeles, Calif., August 2001 (pages 1-8); and Sander et al., xe2x80x9cSilhouette Clipping,xe2x80x9d SIGGRAPH 2000, New Orleans, La., July 2000 (pages 1-8). The progressive hull approach described in the Buehler and Sander articles has significant deficiencies. At the very least, the approach does not apply generally to all types of object shapes. This progressive hull approach cannot handle concave proxies, or objects that have parts close to each other or touching each other. In addition, this approach is not well suited for mixing image-based rendering (ibr) objects with regular scenes.
What is needed is a method and system for forming object proxies which can be used with all types of object shapes.
The present invention overcomes each of the above-identified problems and has additional advantages as described herein. The present invention provides a system, method and computer program product for forming object proxies. In one embodiment, a method forms an object proxy that approximates the geometry of an object. The method includes forming a volume that encompasses the object, forming an isosurface within the volume, adjusting the isosurface relative to a surface of the object, and pruning the isosurface to obtain the object proxy. The formed volume is made up of voxels that encompass the object. The isosurface forming step includes determining sets of vertices for the voxels such that the sets of vertices define polygons representing the isosurface at a first distance from the surface of the object.
According to a feature of the method of the present invention, the isosurface adjusting step includes adjusting at least some of the vertices of the isosurface until each vertex is at or near a second distance from the surface of the object. In one embodiment, each vertex is iteratively advanced by an amount based on a first distance, a second distance, and direction information.
According to a further feature, the isosurface pruning step includes pruning the isosurface based on a distance condition and an intersection condition. In one embodiment, a list of vertices of the isosurface is iteratively pruned. This pruning includes selecting a vertex, and determining whether the selected vertex can be eliminated from the isosurface based on a distance condition and an intersection condition. When a selected vertex can be eliminated, the vertex is eliminated and new edges are created using remaining vertices.
Another feature of the method includes a step of iteratively moving vertices in the initial object proxy closer to the surface of the object. In one example, after pruning to obtain an initial object proxy, the distance of a respective vertex to the object surface is computed. Each vertex of the initial object proxy is advanced toward the object surface until each vertex is on or near the object surface with no polygons deeper than a predetermined distance or until a predetermined number of iterations has been reached.
According to further feature, object proxy formation parameters can be user-specified and/or predetermined. These object proxy formation parameters include: a grid resolution (N1xc3x97N2xc3x97N3) representing the resolution of voxels in a volume, a first distance value (D1) representing the first distance between an initial isosurface and the object surface, a second distance value (D2) representing the distance between an initial object proxy obtained after pruning and the object surface, a third distance value (D3) representing the maximum allowed distance between a vertice in the isosurface and the object surface during pruning, and a fourth distance value (D4) representing a maximum depth for vertices from the object surface.
The present invention also provides an apparatus for forming an object proxy that approximates the geometry of an object. The apparatus includes an isosurface former that forms an isosurface within a volume encompassing an object, and an isosurface shaper that adjusts the isosurface relative to the surface of the object and prunes the isosurface to obtain the object proxy.
Other embodiments include a system and a computer program product. The system forms an object proxy that approximates the geometry of an object. The system includes: means for forming a volume that encompasses the object; means for forming an isosurface within the volume; means for adjusting the isosurface relative to a surface of the object; and means for pruning the isosurface to obtain the object proxy. The computer program product includes computer usable media having computer readable program code embodied in said media for causing a processor to form an object proxy. The computer readable program code has first program code that enables the processor to form a volume that encompasses the object; second program code that enables the processor form an isosurface within the volume; third program code that enables the processor to adjust the isosurface relative to a surface of the object; and fourth program code that enables the processor to prune the isosurface to obtain the object proxy.
The present invention has general application as it can be used to form object proxies for all types of object shapes. The present invention also forms an object proxy that approximates object geometry and reduces the processing work required at run-time. For example, the object proxy can have less polygons and associated vertices than the original object. In this way, rendering of the object based on the object proxy can be carried out for display or animation in real-time at an interactive rate even on cheaper graphics hardware. Compared to a general mesh simplification algorithm, object proxies formed according to the present invention are assured to have no or minimal interaction with an object, which is especially advantageous in hardware-accelerated image-based rendering.
Another advantage is that present invention allows object formation parameters to be user-specified (or set by default) so that the degree in which the isosurface shape approximates the original object surface can be adjusted depending upon a particular application or need. Forming object proxies according to the present invention also make it possible both to render more image-based objects in a single computer generated scene and to render these image-based objects using fewer views/textures than conventional image-based rendering schemes.
Further embodiments, features, and advantages of the present invention, as well as the structure and operation of the various embodiments of the present invention are described in detail below with reference to accompanying drawings.